package formal.linkedList;

/**
 * 奇偶链表
 * 原地算法：不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入的一种算法操作
 *
 * @author DengYuan2
 * @create 2021-01-09 15:49
 */
public class M_328 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        ListNode n7 = new ListNode(7);
        ListNode n8 = new ListNode(8);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next=n8;
        ListNode listNode = oddEvenList2(n1);
        System.out.println(listNode);
    }

    /**
     * 我的写法-将链表分成一个奇数链表，一个偶数链表，两个链表再连起来
     * @param head
     * @return
     */
    public static ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode oddHead = new ListNode(-1);
        ListNode oddTmp = oddHead;
        ListNode evenHead = new ListNode(-1);
        ListNode evenTmp = evenHead;
        ListNode slow = head;
        ListNode fast = slow.next;
        while (slow!=null&&fast!=null){
            oddTmp.next=slow;
            oddTmp=oddTmp.next;
            slow=fast.next;
            evenTmp.next=fast;
            evenTmp = evenTmp.next;
            if (slow!=null){
                fast=slow.next;
            }
        }
        oddTmp.next=null;
        evenTmp.next=null;
        if (slow!=null){
            oddTmp.next=slow;
            oddTmp=oddTmp.next;
        }
        oddTmp.next=evenHead.next;
        return oddHead.next;
    }

    /**
     * 官方-大致思想一致，但他是利用原有的链构造奇数链表
     * @param head
     * @return
     */
    public static ListNode oddEvenList2(ListNode head){
        if (head==null){
            return head;
        }
        ListNode evenHead = head.next;
        ListNode odd = head;
        ListNode even = head.next;
        while (even!=null&&even.next!=null){
            odd.next=even.next;
            odd=odd.next;
            even.next=odd.next;
            even=even.next;
        }
        odd.next=evenHead;
        return head;
    }
}
